This invention relates generally to computer systems and more particularly to computer systems having central processing units (CPUs) employing multiple level cache memories.
As is known in the art, computer systems generally include at least one central processing unit and a memory interconnected by a system bus. In a typical computer system implementation, instructions and data are stored in the same memory. The processor fetches instructions from the memory and executes operations on data as specified by the fetched instructions. As the speed of processors has increased, a need has arisen to find ways to more suitably match the access time of the main computer memory to the computational speed of the processor.
One known way of accomplishing this is through the use of cache memory. As is known in the art, cache memory typically includes a small, high-speed buffer memory used to temporarily hold those portions of the contents of main memory most likely to be used by the CPU in the near future. Since cache memory typically has a much faster access time than main memory, a CPU with a cache memory system spends much less time waiting for instructions and operands to be fetched and/or stored. In multi-processor computer systems, each CPU is typically provided with its own cache or cache system.
A cache memory contains a subset of the information stored in main memory and typically resides on the data path between the processing unit and the system bus. The system bus is used by the CPU to communicate with the main memory as well as other processors in a computer system. When a processor attempts to access a main memory location whose contents (data) have been copied to the cache, no access to main memory is required in order to provide the requested data to the CPU. The required data will be supplied from the cache as long as the data contained in the cache is valid. Since access to the cache is faster than access to main memory the processor can resume operations more quickly. The event where requested data is found in the cache is commonly referred to as a "cache hit".
On the other hand, when the processor attempts to access a main memory location that has not had its contents copied to the cache or a cache location which includes invalid data, a main memory access is initiated by the CPU to obtain the desired data. This event is commonly referred to as a "cache miss". As the result of a cache miss, a main memory access occurs and the data read from main memory is sent to both the processor and to the cache so that subsequent attempts to access the same memory location will result in cache hits. In this way, the effective memory access time for the processor is reduced to a value somewhere between the fast access time of the cache memory and the slower access time of main memory.
One way in which caches are categorized is by the manner in which data placed in a cache is updated to main memory or another cache. This is also commonly referred to as the update protocol. Generally, caches fall into two categories of update protocol. The first category of caches are so called "write-through" caches. With a write-through cache, data is copied to main memory or the next level cache at the same time or very soon after it is written to the cache. The second category of caches are so called "write-back" caches. With a write-back cache, data placed in the cache is not immediately copied to main memory or next level cache.
Although the use of write-back caches typically results in a faster memory system, there is generally an increased complexity in the memory design in order to maintain cache coherency. Since modified data in a write-back cache is not immediately copied to main memory or other cache memory, there is potential for other processors of a multi-processor system to use an older version of a data item. Maintaining cache coherency involves ensuring that all processor always use the most recent version of data from a cache or main memory.
Maintaining cache coherence is of particular concern in a multi-processor systems. This problem arises since the value stored in a single cache memory location might, at one time, be replicated in the local cache memory of any or all of the processors. If each local cache memory employs a write-back policy (i.e. writing modified data back to a local cache and not main memory), the system must somehow ensure that when one processor modifies the value of a memory location and writes that modification only to its own local cache memory, then the copies of that memory location in any of the other local caches should reflect the change made by that one processor. Additionally, at some point, the modified data must be copied back to the main memory. In a write-back cache design, the modified data is known as dirty data.
In order to balance cache speed and size, it is useful to provide more than one level of write-back cache in a computer system. With such a system, it is possible for modified copies of data to exist in each cache level. Thus, the problem of maintaining cache coherency is exacerbated with processor designs where each processor uses multiple levels of cache to implement a cache system.
Although prior art systems have employed processors with multiple level caches, the problem of maintaining coherency between multiple cache levels has been avoided through the use of direct mapped write-through caches. Using direct mapped write-through caches at the first level ensures that the most recent version of data can be found by looking in one place. However, using a write-back cache as the first level cache memory required prior art systems to check each level of write-back cache to determine which cache entry held the appropriate data. The necessity of searching each level of cache for the correct version of data consumes additional time and requires added complexity to the overall cache design.
It would be advantageous to provide a computer system which employs write-back caches to be able to locate the most recent copy of write-back cache data in a simplified manner that does not consume additional time during accesses to the cache.